Parenthesis Matching (Practice Interview Question)

You're out of free questions.

I like parentheticals (a lot).

"Sometimes (when I nest them (my parentheticals) too much (like this (and this))) they get confusing."

Write a function that, given a sentence like the one above, along with the position of an opening parenthesis, finds the corresponding closing parenthesis.

Example: if the example string above is input with the number 10 (position of the first parenthesis), the output should be 79 (position of the last parenthesis).

Gotchas

We can do this in $O(n)$ time.

We can do this in $O(1)$ additional space.

Breakdown

How would you solve this problem by hand with an example input?

Try looping through the string, keeping a count of how many open parentheses we have.

Solution

We simply walk through the string, starting at our input opening parenthesis position. As we iterate, we keep a count of how many additional "(" we find as open_nested_parens. When we find a ")" we decrement open_nested_parens. If we find a ")" and open_nested_parens is 0, we know that ")" closes our initial "(", so we return its position.

  def get_closing_paren(sentence, opening_paren_index):
    open_nested_parens = 0

    for position in range(opening_paren_index + 1, len(sentence)):
        char = sentence[position]

        if char == '(':
            open_nested_parens += 1
        elif char == ')':
            if open_nested_parens == 0:
                return position
            else:
                open_nested_parens -= 1

    raise Exception("No closing parenthesis :(")

Complexity

$O(n)$ time, where $n$ is the number of chars in the string. $O(1)$ space.

The for loop with range keeps our space cost at $O(1)$ . It might be more Pythonic to use:

  for char in sentence[position:]:

Python 2.7

but then our space cost would be $O(n)$ , because in the worst case position would be 0 and we'd take a slice ↴

Array slicing involves taking a subset from an array and allocating a new array with those elements.

In Python 3.6 you can create a new list of the elements in my_list, from start_index to end_index (exclusive), like this:

  my_list[start_index:end_index]

Python 2.7

You can also get everything from start_index onwards by just omitting end_index:

  my_list[start_index:]

Python 2.7

Careful: there's a hidden time and space cost here! It's tempting to think of slicing as just "getting elements," but in reality you are:

allocating a new list
copying the elements from the original list to the new list

This takes $O(n)$ time and $O(n)$ space, where $n$ is the number of elements in the resulting list.

That's a bit easier to see when you save the result of the slice to a variable:

  tail_of_list = my_list[1:]

Python 2.7

But a bit harder to see when you don't save the result of the slice to a variable:

  return my_list[1:]
# Whoops, I just spent O(n) time and space!

Python 2.7

  for item in my_list[1:]:
    # Whoops, I just spent O(n) time and space!
    pass

Python 2.7

So keep an eye out. Slice wisely.

of the entire input.

What We Learned

The trick to many "parsing" questions like this is using a stack to track which brackets/phrases/etc are "open" as you go.

So next time you get a parsing question, one of your first thoughts should be "use a stack!"

In this problem, we can realize our stack would only hold '(' characters. So instead of storing each of those characters in a stack, we can store the number of items our stack would be holding.

That gets us from $O(n)$ space to $O(1)$ space.

It's pretty cool when you can replace a whole data structure with a single integer :)

Do you have an answer?

Show answer

I have an answer Tell me more

Wanna review this one again later? Or do you feel like you got it all?

Mark as done Pin for review later

You're out of free questions.

Gotchas

Breakdown

Solution

Complexity

What We Learned

Programming interview questions by company:

Programming interview questions by topic: